P6055 [RC-02] GCD

这道题的反推还是挺有意思的。

i=1nj=1np=1njq=1nj[(i,j)=1][(p,q)=1]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

i=1nj=1np=1nq=1n[(i,j)=1][(p,q)=j]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{n}\sum_{q=1}^{n}[(i,j)=1][(p,q)=j]

i=1np=1nq=1n[(i,p,q)=1]\sum_{i=1}^n\sum_{p=1}^{n}\sum_{q=1}^{n}[(i,p,q)=1]

然后就可以正常化简了。

i=1np=1nq=1n[(i,p,q)=1]\sum_{i=1}^n\sum_{p=1}^{n}\sum_{q=1}^{n}[(i,p,q)=1]

d=1nμ(d)nd3\sum_{d=1}^n \mu(d) \lfloor \frac{n}{d} \rfloor ^3

整除分块+杜教筛即可。

#include <map>
#include <cstdio>
using namespace std;

const int MAXN = 2e6 , Mod = 998244353;

int prn , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , f[ MAXN + 5 ]; 
bool vis[ MAXN + 5 ];
void sieve( ) {
	mu[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) prime[ ++ prn ] = i , mu[ i ] = -1;
		for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) break;
			mu[ i * prime[ j ] ] = -mu[ i ];
		}
	}
	for( int i = 1 ; i <= MAXN ; i ++ ) f[ i ] = f[ i - 1 ] + mu[ i ];
}

map< int , int > Smu;
int Summu( int n ) {
    if( n <= MAXN ) return f[ n ];
    if( Smu[ n ] ) return Smu[ n ];

    int Ans = 1;
    for( int l = 2 , r ; l <= n ; l = r + 1 ) {
        r = n / ( n / l );
        Ans -= ( r - l + 1 ) * Summu( n / l );
    }
    return Smu[ n ] = Ans;
}

int Solve( int n ) {
    int Ans = 0;
    for( int l = 1 , r ; l <= n ; l = r + 1 ) {
        r = n / ( n / l );
        Ans = ( Ans + 1ll * ( ( Summu( r ) - Summu( l - 1 ) ) % Mod + Mod ) % Mod * ( n / l ) % Mod * ( n / l ) % Mod * ( n / l ) % Mod ) % Mod;
    }
    return Ans;
}

int n;
int main( ) {
	sieve( );
    scanf("%d",&n);
    printf("%d\n", Solve( n ) );
	return 0;
}